In the context of raster-based graphical systems, a polygon is typically defined by a number of points or vertices, where the vertices are interconnected by a plurality of segments forming the polygon. A path consists of a plurality of edges and therefore substantially comprises a general polygon set. Each path has an associated fill rule, which determines how the edges of the path are filled when rendered. Fill rules are generally based on a winding count for a path where a winding count is a value that counts the number of line segments crossed as a straight line is projected through the path.
Set operations are commonly used on graphical objects as a pre-processing step in order to optimize further downstream processing of the graphical objects. Set operations can be used to combine two or more polygons before they are rendered or triangularized. For example, set operations are commonly used during clipping of graphical objects. Clipping is the process of selecting an area or portion of a graphical object to be included in a final representation of the graphical object. Clipping can also be used to discard an unwanted area or portion of a subject graphical object, where the discarded portion is not included in a final representation of the graphical object. Graphical objects are commonly represented by a polygon set and as such clipping is commonly executed on graphical objects using set operations such as intersection, union and difference operations.
There are several known path processing methods which perform set operations on polygons. Most of these methods are based on a particular set operation (e.g. intersection) and are only optimized for paths of certain simple shapes such as squares or straight lines using simple set operations. However, some of these known path processing methods are configured to perform a variety of set operations. The methods that perform a variety of set operations, however, require complex data structures and generally assume that an input polygon conforms to certain characteristics such as being simple and convex. Further, many of these known path processing methods can not handle degenerate cases such as segment starts/ends on other segments and/or co-linear segments.
Still further, many of the existing path processing methods, such as “scan conversion” and “triangulation”, suffer from constraints in path complexity and fill rule, and are only able to handle paths with specific fill rules and complexity. Such path processing methods can only achieve optimum processing speed when input paths are relatively simple and do not always produce simple outline paths.